// https://www.lintcode.com/problem/longest-word-in-dictionary/

public class Solution {
    /**
     * @param words: a list of strings
     * @return: the longest word in words that can be built one character at a time by other words in words
     */
    public String longestWord(String[] words) {
        // Write your code here
        String ret = "";
        int len = -1;
        HashSet<String> set = new HashSet<>();
        for (String word : words) {
            set.add(word);
        }
        for (String word : words) {
            int wl = word.length();
            while (wl > 0) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < wl; ++j) {
                    sb.append(word.charAt(j));
                }
                if (!set.contains(sb.toString())) {
                    break;
                }
                --wl;
            }
            if (wl == 0) {
                if (word.length() > len) {
                    len = word.length();
                    ret = word;
                } else if (word.length() == len) {
                    if (word.compareTo(ret) < 0) {
                        ret = word;
                    }
                }
            }
        }
        return ret;
    }
}